643. 子数组最大平均数 I - 力扣（LeetCode）

Similar Question

leading to the advanced question

Solution Tips

方案一: 滑动窗口

var findMaxAverage = function(nums, k) {
    // 窗口长度是 k, 维护窗口的数据结构直接用一个常数变量即可, 窗口滑动时先减去再加上
    let windowSum = 0;
    let count = 0;
    while (count < k) {
        windowSum += nums[count];
        count++
    }
    let max = windowSum;

    for (let i = k; i < nums.length; i++) {
        // 减去一个, 加上一个
        windowSum -= nums[i - k];
        windowSum += nums[i];

        max = Math.max(windowSum, max)
    }

    return (max / k).toFixed(5)
};

let nums = [1,12,-5,-6,50,3], k = 4
console.log(findMaxAverage(nums, k))

方案二: 前缀和

本题求连续子数组，故第一反应就应该想到滑动窗口，而这题求平均数最大，数的个数又最大，也就是说，窗口 k 里的和最大，使用滑动窗口很容易求解。不过这题数组又没有变化，又涉及到子数组求和，那么自然也可以想到前缀和数组。

也就是说，求 [i,i+k-1] 区间和的最大值，那么直接对 i 遍历求 presum[i+k]-presum[i] 的最大值即可。

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        vector<int> presum(nums.size()+1);
        presum[0]=0;
        for(int i=1;i<presum.size();i++){
            presum[i]=presum[i-1]+nums[i-1];
        }

        int sum=-9999999999;

        for(int i=0;i<presum.size()-k;i++){
            if (presum[i+k]-presum[i] > sum){
                sum=presum[i+k]-presum[i];
            }
        }

        return (double)sum/k;
    }
};